package com.chj.gaoji.class12.test;

import java.util.Arrays;

//http://www.chenxii.cn/2020/03/08/D-DataStructureAndAlgorithm/E-ZuoInterview/144-draw/
public class Code01_SplitArrayLargestSum {

	public static int splitArray1(int[] nums, int m) {
		return process(nums, 0, m);
	}

	public static int process(int[] arr, int index, int part) {
		if (index == arr.length) {
			return 0;
		}
		if (part == 0) {
			return -1;
		}
		int first = 0;
		int min = Integer.MAX_VALUE;
//		for (int end = index; arr.length - end >= part; end++) {
//			first += arr[end];
//			int next = process(arr, end + 1, part - 1);
//			if (next != -1) {
//				min = Math.min(min, Math.max(first, next));
//			}
//		}

		for (int end = index; end <= arr.length - part; end++) {
			first += arr[end];
			int next = process(arr, end + 1, part - 1);
			if (next != -1) {
				min = Math.min(min, Math.max(first, next));
			}
		}
		return min;
	}

	public static int splitArray2(int[] nums, int M) {
		int N = nums.length;
		int[] help = new int[nums.length + 1];
		for (int i = 0; i < N; i++) {
			help[i + 1] = help[i] + nums[i];
		}
		int[][] dp = new int[N][M + 1];
		for (int i = 0; i < N; i++) {
			dp[i][1] = help[i + 1] - help[0];
		}
		for (int i = 1; i < Math.min(N, M); i++) {
			dp[i][i + 1] = Math.max(dp[i - 1][i], nums[i]);
		}

		for (int j = 2; j < dp[0].length; j++) {
			for (int i = dp.length - 1; i >= 2; i--) {
				dp[i][j] = Integer.MAX_VALUE;
				for (int k = 0; k <= i; k++) {
					int helpTemp = help[i + 1] - help[i - k + 1];
					int curAns = Math.max(dp[i - k][j - 1], helpTemp);
					dp[i][j] = Math.min(dp[i][j], curAns);
				}
			}
		}
		return dp[N - 1][M];
	}

	public static int splitArray3(int[] nums, int M) {
		int N = nums.length;
		int[] help = new int[nums.length + 1];
		for (int i = 0; i < N; i++) {
			help[i + 1] = help[i] + nums[i];
		}
		int[][] dp = new int[N][M + 1];
		int[][] best = new int[N][M + 1];
		for (int i = 0; i < N; i++) {
			dp[i][1] = help[i + 1] - help[0];
		}
		for (int i = 1; i < Math.min(N, M); i++) {
			dp[i][i + 1] = Math.max(dp[i - 1][i], nums[i]);
			best[i][i + 1] = i;
		}

		for (int i = 2; i < N; i++) {
			for (int j = Math.min(i, M); j >= 2; j--) {
				dp[i][j] = Integer.MAX_VALUE;
				int left = best[i - 1][j];
				int right = j + 1 > M ? i : best[i][j + 1];
				for (int k = left; k <= right; k++) {
					int curAns = Math.max(dp[k - 1][j - 1], help[i + 1] - help[k]);
					if (dp[i][j] > curAns) {
						dp[i][j] = curAns;
						best[i][j] = k;
					}
				}
			}
		}

		return dp[N - 1][M];
	}

	public static int splitArray4(int[] nums, int M) {
		long sum = 0;
		for (int i = 0; i < nums.length; i++) {
			sum += nums[i];
		}
		long l = 0;
		long r = sum;
		long ans = 0;
		while (l <= r) {
			long mid = (l + r) / 2;
			long cur = getNeedParts(nums, mid);
			if (cur <= M) {
				ans = mid;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return (int) ans;
	}

	public static int getNeedParts(int[] arr, long aim) {
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] > aim) {
				return Integer.MAX_VALUE;
			}
		}
		int parts = 1;
		int all = arr[0];
		for (int i = 1; i < arr.length; i++) {
			if (all + arr[i] > aim) {
				parts++;
				all = arr[i];
			} else {
				all += arr[i];
			}
		}
		return parts;
	}

	// 获得随机的数组
	public static int[] generateRandomArray(int length) {
		int[] result = new int[length];
		for (int i = 0; i != result.length; i++) {
			result[i] = (int) (Math.random() * 10) + 1;
		}
		return result;
	}

	// 打印数组
	public static void printArray(int[] arr) {
		for (int i = 0; i != arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	// for test
	public static int[] getSortedArray(int len, int range) {
		int[] arr = new int[len];
		for (int i = 0; i != len; i++) {
			arr[i] = (int) (Math.random() * range);
		}
		Arrays.sort(arr);
		return arr;
	}

	public static void main(String[] args) {

		// System.out.println("Hello");
		int[] arr2 = { 1, 1, 3, 3, 4 }; // 总共的作品数
		int num = 2; // 总共的画匠的人数
		System.out.println(splitArray1(arr2, num));
		System.out.println(splitArray2(arr2, num));
		System.out.println(splitArray3(arr2, num));
		System.out.println(splitArray4(arr2, num));

//		int[] arr = generateRandomArray(300);
		// int[]arr={1,1,3,3,4};
//		int painterNum = 2;
		int[] arr = { 1, 1, 1, 4, 3 };
		int painterNum = 3;
		System.out.println(splitArray1(arr, painterNum));
		System.out.println(splitArray2(arr, painterNum));
		System.out.println(splitArray3(arr, painterNum));
		System.out.println(splitArray4(arr, painterNum));

		arr = generateRandomArray(1000000);
		painterNum = 10000;
		long start = System.currentTimeMillis();
		System.out.println(splitArray4(arr, painterNum));
		long end = System.currentTimeMillis();
		System.out.println("cost time: " + (end - start) + " ms");

		System.out.println("radom test");
		{
			int times = 100; // test time
			int len = 1000; // test array length
			int range = 2000; // every number in [0,range)
			int p = 50; // post office number
			long time1 = 0; // method1 all run time
			long time2 = 0;// method2 all run time
			long start11 = 0;
			long end11 = 0;
			int res1 = 0;
			int res2 = 0;
			for (int i = 0; i != times; i++) {
				arr = getSortedArray(len, range);
				start11 = System.currentTimeMillis();
				res1 = splitArray2(arr, p);
				end11 = System.currentTimeMillis();
				time1 += end11 - start11;
				start11 = System.currentTimeMillis();
				res2 = splitArray3(arr, p);
				end11 = System.currentTimeMillis();
				time2 += end11 - start11;
				if (res1 != res2) {
					printArray(arr);
					break;
				}
				if (i % 10 == 0) {
					System.out.print(". ");
				}
			}

			System.out.println();
			System.out.println("method1 all run time(ms): " + time1);
			System.out.println("method2 all run time(ms): " + time2);
		}
	}

}
